Gates thực hiện một nỗ lực khó khăn là thuyết phục đồng minh tiếp tục duy trì sự hỗ trợ cho cuộc chiến Afghanistan ngay cả trong khi chính quyền Barack Obama tiếp tục tranh cãi về việc có nên gửi thêm quân đến nơi này hay không. Chính cá nhân Gates cũng chưa loan báo về quyết định của ông - ít nhất là trước công chúng - về việc gửi thêm quân đến Afghanistan theo như yêu cầu của tư lệnh chiến trường hay tập trung nỗ lực nhắm vào thành phần khủng bố al-Qaeda ẩn náu tại Pakistan.

Gates lên đường ngày 18 tháng 10 năm 2009 để khởi sự chuyến công du kéo dài một tuần qua Nhật, Hàn Quốc và Slovakia - nhằm kêu gọi các đồng minh NATO tiếp tục đóng góp vào cuộc chiến đã sang đến năm thứ chín. Có lẽ vì biết rằng phải kêu gọi sự hỗ trợ của các quốc gia khác trong khi chính Hoa Kỳ cũng chưa có quyết định, Gates không chỉ hỏi xin viện trợ quân sự. "Có nhiều hình thức đóng góp giá trị ở Afghanistan như trong lãnh vực phát triển và huấn luyện, với lực lượng cảnh sát và mọi phương diện khác trong đời sống dân sự," một viên chức cao cấp Bộ Quốc phòng Hoa Kỳ tuyên bố với báo chí.

Tuy nhiên, các đồng minh tính đến chuyện rút lui. Nhật Bản rút hai chiến hạm khỏi vùng Ấn Ðộ Dương từng làm nhiệm vụ tiếp tế dầu cho các chiến hạm trên đường tới Afghanistan. Anh vào giữa tháng 10/2009 tuyên bố sẽ gửi thêm một lực lượng nhỏ, nhưng có giá trị biểu kiến, gồm 500 quân - với điều kiện là NATO và chính quyền Afghanistan phải có thêm cố gắng chống Taliban.

Giới chức quốc phòng Hoa Kỳ nói Gates thảo luận quyết định rút tàu chiến Nhật ra khỏi nhiệm vụ tiếp tế nhiên liệu khi ông tới Tokyo ngày 20 tháng 10 năm 2009. Tuy nhiên Gates không trông đợi sẽ thay đổi được ý kiến của Thủ tướng Nhật Yukio Hatoyama, người vừa lên cầm quyền tháng 9 năm 2009 và muốn Nhật đi theo phương cách khác để tái lập hòa bình ở Afghanistan.